Gram matrix

 ( Systems Theory ) 

In linear algebra, the Gram matrix (or Gramian matrix, Gramian) of a set of vectors $v\_1,\backslash dots,\; v\_n$ in an inner product space is the Hermitian matrix of , whose entries are given by the inner product $G\_\{ij\}\; =\; \backslash left\backslash langle\; v\_i,\; v\_j\; \backslash right\backslash rangle$., p.441, Theorem 7.2.10 If the vectors $v\_1,\backslash dots,\; v\_n$ are the columns of matrix $X$ then the Gram matrix is $X^\backslash dagger\; X$ in the general case that the vector coordinates are complex numbers, which simplifies to $X^\backslash top\; X$ for the case that the vector coordinates are real numbers.

An important application is to compute linear independence: a set of vectors are linearly independent if and only if the Gram determinant (the determinant of the Gram matrix) is non-zero.

It is named after Jørgen Pedersen Gram.

---

Examples For finite-dimensional real vectors in $\backslash mathbb\{R\}^n$ with the usual Euclidean dot product, the Gram matrix is $G\; =\; V^\backslash top\; V$, where $V$ is a matrix whose columns are the vectors $v\_k$ and $V^\backslash top$ is its transpose whose rows are the vectors $v\_k^\backslash top$. For complex number vectors in $\backslash mathbb\{C\}^n$, $G\; =\; V^\backslash dagger\; V$, where $V^\backslash dagger$ is the conjugate transpose of $V$.

Given square-integrable functions $\backslash \{\backslash ell\_i(\backslash cdot),\backslash ,\; i\; =\; 1,\backslash dots,n\backslash \}$ on the interval $\backslash leftt\_0,$, the Gram matrix $G\; =\; \backslash leftG\_\{ij\}\backslash right$ is:

$G\_\{ij\}\; =\; \backslash int\_\{t\_0\}^\{t\_f\}\; \backslash ell\_i^*(\backslash tau)\backslash ell\_j(\backslash tau)\backslash ,\; d\backslash tau.$

where $\backslash ell\_i^*(\backslash tau)$ is the complex conjugate of $\backslash ell\_i(\backslash tau)$.

For any bilinear form $B$ on a finite-dimensional vector space over any field we can define a Gram matrix $G$ attached to a set of vectors $v\_1,\; \backslash dots,\; v\_n$ by $G\_\{ij\}\; =\; B\backslash left(v\_i,\; v\_j\backslash right)$. The matrix will be symmetric if the bilinear form $B$ is symmetric.

---

Applications

• In Riemannian geometry, given an embedded $k$-dimensional Riemannian manifold $M\backslash subset\; \backslash mathbb\{R\}^n$ and a parametrization $\backslash phi:\; U\backslash to\; M$ for the volume form $\backslash omega$ on $M$ induced by the embedding may be computed using the Gramian of the coordinate tangent vectors: $$\backslash omega\; =\; \backslash sqrt\{\backslash det\; G\}\backslash \; dx\_1\; \backslash cdots\; dx\_k,\backslash quad\; G\; =\; \backslash left\backslash left\backslash langle.$$ This generalizes the classical surface integral of a parametrized surface $\backslash phi:U\backslash to\; S\backslash subset\; \backslash mathbb\{R\}^3$ for $(x,\; y)\backslash in\; U\backslash subset\backslash mathbb\{R\}^2$: $$\backslash int\_S\; f\backslash \; dA\; =\; \backslash iint\_U\; f(\backslash phi(x,\; y))\backslash ,\; \backslash left|\backslash frac\{\backslash partial\backslash phi\}\{\backslash partial\; x\}\backslash ,\{\backslash times\}\backslash ,\backslash frac\{\backslash partial\backslash phi\}\{\backslash partial\; y\}\backslash right|\backslash ,\; dx\backslash ,\; dy.$$
• If the vectors are centered , the Gramian is approximately proportional to the covariance matrix, with the scaling determined by the number of elements in the vector.
• In quantum chemistry, the Gram matrix of a set of basis vectors is the overlap matrix.
• In control theory (or more generally systems theory), the controllability Gramian and observability Gramian determine properties of a linear system.
• Gramian matrices arise in covariance structure model fitting (see e.g., Jamshidian and Bentler, 1993, Applied Psychological Measurement, Volume 18, pp. 79–94).
• In the finite element method, the Gram matrix arises from approximating a function from a finite dimensional space; the Gram matrix entries are then the inner products of the basis functions of the finite dimensional subspace.
• In machine learning, are often represented as Gram matrices. (Also see kernel PCA)
• Since the Gram matrix over the reals is a symmetric matrix, it is diagonalizable and its eigenvalues are non-negative. The diagonalization of the Gram matrix is the singular value decomposition.

---

Properties

---

Positive-semidefiniteness The Gram matrix is symmetric matrix in the case the inner product is real-valued; it is Hermitian matrix in the general, complex case by definition of an inner product.

The Gram matrix is positive semidefinite, and every positive semidefinite matrix is the Gramian matrix for some set of vectors. The fact that the Gramian matrix is positive-semidefinite can be seen from the following simple derivation:

$$

 x^\dagger \mathbf{G} x =
 \sum_{i,j}x_i^* x_j\left\langle v_i, v_j \right\rangle =
 \sum_{i,j}\left\langle x_i v_i, x_j v_j \right\rangle =
 \biggl\langle \sum_i x_i v_i, \sum_j x_j v_j \biggr\rangle =
 \biggl\| \sum_i x_i v_i \biggr\|^2 \geq 0 .
     

The first equality follows from the definition of matrix multiplication, the second and third from the bi-linearity of the inner-product, and the last from the positive definiteness of the inner product. Note that this also shows that the Gramian matrix is positive definite if and only if the vectors $v\_i$ are linearly independent (that is, $\backslash sum\_i\; x\_i\; v\_i\; \backslash neq\; 0$ for all $x$).

---

Finding a vector realization Given any positive semidefinite matrix $M$, one can decompose it as:

$M\; =\; B^\backslash dagger\; B$,

where $B^\backslash dagger$ is the conjugate transpose of $B$ (or $M\; =\; B^\backslash textsf\{T\}\; B$ in the real case).

Here $B$ is a $k\; \backslash times\; n$ matrix, where $k$ is the matrix rank of $M$. Various ways to obtain such a decomposition include computing the Cholesky decomposition or taking the non-negative square root of $M$.

The columns $b^\{(1)\},\; \backslash dots,\; b^\{(n)\}$ of $B$ can be seen as n vectors in $\backslash mathbb\{C\}^k$ (or k-dimensional Euclidean space $\backslash mathbb\{R\}^k$, in the real case). Then

$M\_\{ij\}\; =\; b^\{(i)\}\; \backslash cdot\; b^\{(j)\}$

where the dot product $a\; \backslash cdot\; b\; =\; \backslash sum\_\{\backslash ell=1\}^k\; a\_\backslash ell^*\; b\_\backslash ell$ is the usual inner product on $\backslash mathbb\{C\}^k$.

Thus a Hermitian matrix $M$ is positive semidefinite if and only if it is the Gram matrix of some vectors $b^\{(1)\},\; \backslash dots,\; b^\{(n)\}$. Such vectors are called a vector realization of The infinite-dimensional analog of this statement is Mercer's theorem.

---

Uniqueness of vector realizations If $M$ is the Gram matrix of vectors $v\_1,\backslash dots,v\_n$ in $\backslash mathbb\{R\}^k$ then applying any rotation or reflection of $\backslash mathbb\{R\}^k$ (any orthogonal transformation, that is, any Euclidean isometry preserving 0) to the sequence of vectors results in the same Gram matrix. That is, for any $k\; \backslash times\; k$ orthogonal matrix $Q$, the Gram matrix of $Q\; v\_1,\backslash dots,\; Q\; v\_n$ is also

This is the only way in which two real vector realizations of $M$ can differ: the vectors $v\_1,\backslash dots,v\_n$ are unique up to orthogonal transformations. In other words, the dot products $v\_i\; \backslash cdot\; v\_j$ and $w\_i\; \backslash cdot\; w\_j$ are equal if and only if some rigid transformation of $\backslash mathbb\{R\}^k$ transforms the vectors $v\_1,\backslash dots,v\_n$ to $w\_1,\; \backslash dots,\; w\_n$ and 0 to 0.

The same holds in the complex case, with unitary transformations in place of orthogonal ones. That is, if the Gram matrix of vectors $v\_1,\; \backslash dots,\; v\_n$ is equal to the Gram matrix of vectors $w\_1,\; \backslash dots,\; w\_n$ in $\backslash mathbb\{C\}^k$ then there is a unitary matrix $k\; \backslash times\; k$ matrix $U$ (meaning $U^\backslash dagger\; U\; =\; I$) such that $v\_i\; =\; U\; w\_i$ for $i\; =\; 1,\; \backslash dots,\; n$., p. 452, Theorem 7.3.11

---

Other properties

• Because $G\; =\; G^\backslash dagger$, it is necessarily the case that $G$ and $G^\backslash dagger$ commute. That is, a real or complex Gram matrix $G$ is also a normal matrix.
• The Gram matrix of any orthonormal basis is the identity matrix. Equivalently, the Gram matrix of the rows or the columns of a real rotation matrix is the identity matrix. Likewise, the Gram matrix of the rows or columns of a unitary matrix is the identity matrix.
• The rank of the Gram matrix of vectors in $\backslash mathbb\{R\}^k$ or $\backslash mathbb\{C\}^k$ equals the dimension of the space Linear span by these vectors.

---

Gram determinant The Gram determinant or Gramian is the determinant of the Gram matrix: $$\backslash bigl|G(v\_1,\; \backslash dots,\; v\_n)\backslash bigr|\; =\; \backslash begin\{vmatrix\}$$

 \langle v_1,v_1\rangle & \langle v_1,v_2\rangle &\dots & \langle v_1,v_n\rangle \\
 \langle v_2,v_1\rangle & \langle v_2,v_2\rangle &\dots & \langle v_2,v_n\rangle \\
 \vdots & \vdots & \ddots & \vdots \\
 \langle v_n,v_1\rangle & \langle v_n,v_2\rangle &\dots & \langle v_n,v_n\rangle
     

\end{vmatrix}.

If $v\_1,\; \backslash dots,\; v\_n$ are vectors in $\backslash mathbb\{R\}^m$ then it is the square of the n-dimensional volume of the parallelotope formed by the vectors. In particular, the vectors are linearly independent if and only if the parallelotope has nonzero n-dimensional volume, if and only if Gram determinant is nonzero, if and only if the Gram matrix is nonsingular. When the determinant and volume are zero. When , this reduces to the standard theorem that the absolute value of the determinant of n n-dimensional vectors is the n-dimensional volume. The volume of the simplex formed by the vectors is .

When $v\_1,\; \backslash dots,\; v\_n$ are linearly independent, the distance between a point $x$ and the linear span of $v\_1,\; \backslash dots,\; v\_n$ is $\backslash sqrt\{\backslash frac$

}.

Consider the moment problem: given $c\_1,\; \backslash dots,\; c\_n\; \backslash in\; \backslash mathbb\; C$, find a vector $v$ such that $\backslash left\backslash langle\; v,\; v\_i\backslash right\backslash rangle=c\_i$, for all $1\; \backslash leqslant\; i\; \backslash leqslant\; n$. There exists a unique solution with minimal norm:The Gram determinant can also be expressed in terms of the exterior product of vectors by

$\backslash bigl|G(v\_1,\; \backslash dots,\; v\_n)\backslash bigr|\; =\; \backslash |\; v\_1\; \backslash wedge\; \backslash cdots\; \backslash wedge\; v\_n\backslash |^2.$

The Gram determinant therefore supplies an inner product for the space . If an orthonormal basis e _i, on is given, the vectors

will constitute an orthonormal basis of n-dimensional volumes on the space . Then the Gram determinant $\backslash bigl|G(v\_1,\; \backslash dots,\; v\_n)\backslash bigr|$ amounts to an n-dimensional Pythagorean Theorem for the volume of the parallelotope formed by the vectors $v\_1\; \backslash wedge\; \backslash cdots\; \backslash wedge\; v\_n$ in terms of its projections onto the basis volumes $e\_\{i\_1\}\; \backslash wedge\; \backslash cdots\; \backslash wedge\; e\_\{i\_n\}$.

When the vectors $v\_1,\; \backslash ldots,\; v\_n\; \backslash in\; \backslash mathbb\{R\}^m$ are defined from the positions of points $p\_1,\; \backslash ldots,\; p\_n$ relative to some reference point $p\_\{n+1\}$,

$$(v\_1,\; v\_2,\; \backslash ldots,\; v\_n)\; =\; (p\_1\; -\; p\_\{n+1\},\; p\_2\; -\; p\_\{n+1\},\; \backslash ldots,\; p\_n\; -\; p\_\{n+1\})\backslash ,,$$

then the Gram determinant can be written as the difference of two Gram determinants,

$$$$

\bigl|G(v_1, \dots, v_n)\bigr| = \bigl|G((p_1, 1), \dots, (p_{n+1}, 1))\bigr| - \bigl|G(p_1, \dots, p_{n+1})\bigr|\,, where each $(p\_j,\; 1)$ is the corresponding point $p\_j$ supplemented with the coordinate value of 1 for an $(m+1)$-st dimension. Note that in the common case that , the second term on the right-hand side will be zero.

---

Constructing an orthonormal basis Given a set of linearly independent vectors $\backslash \{v\_i\backslash \}$ with Gram matrix $G$ defined by $G\_\{ij\}:=\; \backslash langle\; v\_i,v\_j\backslash rangle$, one can construct an orthonormal basis

$u\_i\; :=\; \backslash sum\_j\; \backslash bigl(G^\{-1/2\}\backslash bigr)\_\{ji\}\; v\_j.$

In matrix notation, $U\; =\; V\; G^\{-1/2\}$, where $U$ has orthonormal basis vectors $\backslash \{u\_i\backslash \}$ and the matrix $V$ is composed of the given column vectors $\backslash \{v\_i\backslash \}$.

The matrix $G^\{-1/2\}$ is guaranteed to exist. Indeed, $G$ is Hermitian, and so can be decomposed as $G=UDU^\backslash dagger$ with $U$ a unitary matrix and $D$ a real diagonal matrix. Additionally, the $v\_i$ are linearly independent if and only if $G$ is positive definite, which implies that the diagonal entries of $D$ are positive. $G^\{-1/2\}$ is therefore uniquely defined by $G^\{-1/2\}:=UD^\{-1/2\}U^\backslash dagger$. One can check that these new vectors are orthonormal:

$\backslash begin\{align\}$

\langle u_i,u_j \rangle &= \sum_{i'} \sum_{j'} \Bigl\langle \bigl(G^{-1/2}\bigr)_{i'i} v_{i'},\bigl(G^{-1/2}\bigr)_{j'j} v_{j'} \Bigr\rangle \\10mu &= \sum_{i'} \sum_{j'} \bigl(G^{-1/2}\bigr)_{ii'} G_{i'j'} \bigl(G^{-1/2}\bigr)_{j'j} \\8mu &= \bigl(G^{-1/2} G G^{-1/2}\bigr)_{ij} = \delta_{ij} \end{align} where we used $\backslash bigl(G^\{-1/2\}\backslash bigr)^\backslash dagger=G^\{-1/2\}$.

---

See also

• Controllability Gramian
• Observability Gramian

• (2025). 9780521548236, Cambridge University Press. ISBN 9780521548236

---

External links

• Volumes of parallelograms by Frank Jones

Post Comment